Chapter 7
Memory Management

One of the design goals of Cgal (Section 1.1) is efficiency, and this means not only implementing efficient algorithms but also implementing them efficiently. One way to improve the efficiency of an implementation is through efficient memory management. Here we describe one way to address this using the allocator interface.

7.1   The C++ standard allocator interface

We first give a short presentation of the memory allocator interface. Objects of type allocator<T> can be used to obtain small, typed chunks of memory to be used, for example, as static members of a class. This is especially interesting with classes of a constant size that are frequently allocated and deallocated (geometric objects, etc.), since a memory allocator can maintain the corresponding memory chunks in local blocks and thus can answer allocation and deallocation calls much faster than the corresponding system calls. We first recapitulate the interface of an allocator:

7.2   The allocator macro

The macro CGAL_ALLOCATOR is defined in the file <CGAL/memory.h> to be the standard allocator from <memory>. However, the user can redefine it, for example, if Leda is present, he can define it (before including any CGAL header file) this way :

#include <LEDA/allocator.h>
#define CGAL_ALLOCATOR(t) leda_allocator<t>

7.3   Using the allocator

How should a data structure use the allocator mechanism? Just make the allocator one of the template arguments of the data structure. Then use a static member object to allocate items on the heap that you want to keep optimized regarding allocation and deallocation. We show an example using a trivial list structure:

#include <CGAL/memory.h>

template <typename T> 
class dlink 
{ T some_member; };

template < typename T, typename Alloc = CGAL_ALLOCATOR(dlink<T>) >
class list 
{
public:
  typedef dlink<T>* dlink_ptr;
  typedef Alloc list_allocator;

  static list_allocator M;

list() {
  p = M.allocate(1);          // allocation of space for one dlink
  M.construct(p,dlink<T>());  // inplace construction of object
}

~list() {
  M.destroy(p);      // destroy object
  M.deallocate(p,1); // deallocate memory
}

private:
  dlink_ptr p;
};

// init static member allocator object:
template <typename T, typename Alloc>
typename list<T,Alloc>::list_allocator list<T,Alloc>::M =
             typename list<T,Alloc>::list_allocator();


int main()
{
  list<int> L;
  return 0;
}